/**
 * Created by loso on 2017/3/14.
 */
public class _198_HouseRobber {

    public static void main(String[] args) {
        int[] a = new int[]{4,1,2,7,5,3,1};
        System.out.println(rob(a));
    }



    public static int rob(int[] nums){
        int[] nums1;
        if (nums.length % 2 == 1){
            nums1 = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                nums1[i+1] = nums[i];
            }
            nums1[0] = 0;
            nums = nums1;
        }
        boolean isOdd = false;
        int sum = 0;
        int sumdif = 0;

        for (int i = 0; i < nums.length; i=i+2) {
            if (isOdd){
                if(sumdif + nums[i] > nums[i+1]){
                    sum += sumdif + nums[i];
                    isOdd = false;
                }
                else{
                    sumdif += nums[i] - nums[i+1];
                    if (-sumdif > nums[i+1]){
                        sumdif = -nums[i+1];
                    }
                    sum += nums[i+1];
                }
            }
            else{
                if (nums[i]>nums[i+1]){
                    sum += nums[i];
                }
                else{
                    sumdif = nums[i] - nums[i+1];
                    isOdd = true;
                    sum += nums[i+1];
                }
            }
        }
        return sum;
    }

    public static int robyaya1(int[] nums){
        if (nums.length==1){
            return nums[0];
        }else if (nums.length == 2){
            return nums[0]>nums[1]?nums[0]:nums[1];
        }
        nums[1] = nums[0]>nums[1]?nums[0]:nums[1];
        for (int i = 2; i < nums.length; i++) {
            nums[i] = Math.max(nums[i-1],nums[i]+nums[i-2]);
        }
        return nums[nums.length-1];
    }

    public static int robyaya(int[] nums) {
            int[] nums1;
            if (nums.length % 2 == 0){
                nums1 = new int[nums.length + 1];
                for (int i = 0; i < nums.length; i++) {
                    nums1[i+1] = nums[i];
                }
                nums1[0] = 0;
                nums = nums1;
            }
            boolean isOdd = false;
            int sum = 0;
            int sumdif = 0;

            int[] dif = new int[nums.length/2];
        for (int i = 0; i < nums.length / 2; i++) {
            dif[i] = nums[i*2+1] - nums[i*2];
        }
        for (int i = 0; i < dif.length; i++) {
            sumdif +=dif[i];
        }
        for (int i = 0; i <= nums.length/2; i++) {
            sum += nums[i*2];
        }

        for (int i = nums.length/2-1 ; i >= 0 ; i = i-1) {
            if (isOdd){//奇数
                if (sumdif <0){
                    sum -= sumdif;
                }
            }
            else{//偶数
                if(sumdif - nums[2*i+2]>0){
                    sum += sumdif - nums[2*i+2];
                    isOdd = true;
                }
            }
            sumdif -= dif[i];
        }
        return sum;
    }
}
